#include <stdio.h>

int a[1000], sum;

int slove (int n)
{
    int s1, s2;

    if (1 == n) {
        sum += a[0];
    }

    if (2 == n) {
        sum += a[1];
    }

    if (3 == n) {
        sum += a[0] + a[1] + a[2];
    }

    if (4 <= n) {
        s1 = a[0] + 2 * a[1] + a[n-1];
        s2 = 2 * a[0] + a[n-1-1] + a[n-1];

        if (s1 > s2) {
            sum += s2;
        } else {
            sum += s1;
        }
        
        slove(n-2);
    }

    return 0;
}

int main (int argc, char const* argv[])
{

    int i, j, testcase, n;

    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        // sort data
        for (i = 0; i < n-1; i++) {
            for (j = i+1; j < n; j++) {
                if (a[i] > a[j]) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
        }

        sum = 0;
        slove(n);

        printf("%d\n", sum);
    }

    return 0;
}
